//https://leetcode.cn/problems/cut-off-trees-for-golf-event/

class Solution {
    int m, n;
    bool vit[51][51];
    int dx[4] = { 0,0,-1,1 };
    int dy[4] = { -1,1,0,0 };
public:
    int cutOffTree(vector<vector<int>>& forest) {
        //找到要砍树的位置和砍树的顺序
        vector<pair<int, int>> v;
        m = forest.size(), n = forest[0].size();

        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (forest[i][j] > 1)
                    v.push_back({ i,j });
            }
        }

        //按树的高度排序
        sort(v.begin(), v.end(), [&](const pair<int, int>& p1, const pair<int, int>& p2)
            {return forest[p1.first][p1.second] < forest[p2.first][p2.second]; });

        int ret = 0;
        //求从一棵树到另一棵树的最短距离
        int x = 0, y = 0;
        for (auto& [a, b] : v)
        {
            int count = 0;
            count = bfs(forest, x, y, a, b);
            if (count == -1) return -1;
            ret += count;

            x = a;
            y = b;
        }

        return ret;

    }

    int bfs(vector<vector<int>> f, int bx, int by, int ex, int ey)
    {
        if (bx == ex && by == ey) return 0;

        queue<pair<int, int>> q;
        memset(vit, 0, sizeof(vit));

        q.push({ bx,by });
        vit[bx][by] = true;
        int ret = 0;

        while (q.size())
        {
            ret++;
            int sz = q.size();
            while (sz--)
            {
                auto [a, b] = q.front();
                q.pop();

                for (int i = 0; i < 4; i++)
                {
                    int x = a + dx[i];
                    int y = b + dy[i];
                    if (x >= 0 && x < m && y >= 0 && y < n && !vit[x][y] && f[x][y] >= 1)
                    {
                        if (x == ex && y == ey) return ret;

                        q.push({ x,y });
                        vit[x][y] = true;
                    }
                }
            }
        }
        return -1;
    }
};